//硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007) 
//
// 示例 1： 
//
// 
// 输入：n = 5
// 输出：2
// 解释：有两种方式可以凑成总金额:
//5=5
//5=1+1+1+1+1
// 
//
// 示例 2： 
//
// 
// 输入：n = 10
// 输出：4
// 解释：有四种方式可以凑成总金额:
//10=10
//10=5+5
//10=5+1+1+1+1+1
//10=1+1+1+1+1+1+1+1+1+1
// 
//
// 说明： 
//
// 注意: 
//
// 你可以假设： 
//
// 
// 0 <= n (总金额) <= 1000000 
// 
//
// Related Topics 数组 数学 动态规划 👍 298 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-08-31 17:52:01
 * @description 面试题 08.11.硬币
 */
public class CoinLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CoinLcci fun=new CoinLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int waysToChange1(int n) {
        int [] dp=new int[n+1];
		dp[0]=1;
		int [] coins={1,5,10,25};
		int mod=1000000007;
		for(int coin:coins){
			for(int i=coin;i<=n;i++){
				dp[i]=(dp[i]+dp[i-coin])%mod;
			}
		}
		return dp[n];
    }

	// 数学
	/*
	* 先枚举25分的个数i，剩下的部分用10分和5分凑成
	* 剩下的部分rest=n-i*25
	* 10分的个数a最多为rest/10
	* 5分的个数b最多为rest%10/5
	* 对于n，n=25*i+10*a+5*b+1*c
	* 其中0<=i<=n/25
	* 0<=a<=rest/10
	* 0<=b<=rest%10/5
	* 0<=c<=rest%5
	* 对于每一个i，a的取值有rest/10+1种，b的取值有rest%10/5+1种
	* 所以对于每一个i，有(rest/10+1)*(rest%10/5+1)种方法
	* 所以总的方法数为∑(rest/10+1)*(rest%10/5+1)，其中0<=i<=n/25
	* 时间复杂度O(n/25)
	* */
	public int waysToChange(int n) {
		int mod=1000000007;
		int ans = 0;
		for (int i = 0; i * 25 <= n; ++i) {
			int rest = n - i * 25;
			int a = rest / 10;
			int b = rest % 10 / 5;
			ans = (ans + (int) ((long) (a + 1) * (a + b + 1) % mod)) % mod;
		}
		return ans;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
